//给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。 
//
// 最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。 
//
// 你可以假设除了整数 0 之外，这个整数不会以零开头。 
//
// 示例 1: 
//
// 输入: [1,2,3]
//输出: [1,2,4]
//解释: 输入数组表示数字 123。
// 
//
// 示例 2: 
//
// 输入: [4,3,2,1]
//输出: [4,3,2,2]
//解释: 输入数组表示数字 4321。
// 
// Related Topics 数组 
// 👍 529 👎 0

package leetcode.editor.cn;

//Java：加一
public class P66PlusOne {

    /**
     *
     * 思路： 思维定式了，把数组转成了数字，然后加1，然后再转成数组，结果溢出了 =_=，改为long也不行
     *       解决方法是 直接在数组的最后一个+1就行了，如果大于10，则往前进一位，这样就简单了
     *
     * 执行用时： 0 ms , 在所有 Java 提交中击败了 100.00% 的用户 内存消耗： 38.3 MB , 在所有 Java 提交中击败了 22.12% 的用户
     *
     */
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int[] plusOne(int[] digits) {
            boolean flag = true;    // 判断是否每位都是 9，是的话，新的数组长度要加1
            for (int a : digits) {
                if (a != 9) {
                    flag = false;
                    break;
                }
            }

            int len = flag ? digits.length + 1 : digits.length;

            int[] nums = new int[len];

            // 9 9
            for (int i = len - 1, j = digits.length - 1; i >= 0 && j >= 0; i--, j--) {
                int sum;
                // 还得加上前一位进的
                if (i == len - 1 && j == digits.length - 1) {
                    // 首位得加1
                    sum = digits[j] + nums[i] + 1;
                }else{
                    sum = digits[j] + nums[i];
                }
                if (sum < 10) {
                    nums[i] = sum;
                } else {
                    nums[i] = sum % 10;
                    nums[i - 1] = 1;        // 前一位进位
                }
            }
            return nums;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

    public static void main(String[] args) {
        Solution solution = new P66PlusOne().new Solution();
//        int[] nums = new int[]{7, 2, 8, 5, 0, 9, 1, 2, 9, 5, 3, 6, 6, 7, 3, 2, 8, 4, 3, 7, 9, 5, 7, 7, 4, 7, 4, 9, 4, 7, 0, 1, 1, 1, 7, 4, 0, 0, 6};
        int[] nums = new int[]{9};
        System.out.println(solution.plusOne(nums));
        // TO TEST
    }

}